#leetcode题目189：轮转数组
#难度：中等

#方法：数组,双指针

from typing import List

class Solution:
    #leetcode官方题解，
    # def rotate(self, nums: List[int], k: int) -> None:
    #     n = len(nums)
    #     if n == 0:
    #         return
    #     k %= n
    #     new_arr = [0] * n
    #     for i in range(n):
    #         new_arr[(i + k) % n] = nums[i]
    #     # 原地赋值
    #     nums[:] = new_arr
    #     # nums[:] = nums[-k:] + nums[:-k] #切片赋值，原地修改

    # leetcode官方题解2，原地算法，空间复杂度o（1），三次反转法：
    def reverse(self, nums: List[int], start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        if n == 0:
            return
        k %= n
        if k == 0:
            return
        self.reverse(nums, 0, n - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, n - 1)

    #解法来自第三个视频，由java转成python而来。
    #TODO


#测试数据
nums = [1,2,3,4,5,6,7]
k = 3
#预期输出：[5,6,7,1,2,3,4]

solution = Solution()
solution.rotate(nums, k)
print(nums)

nums = [-1,-100,3,99]
k = 2
#预期输出：[3,99,-1,-100]

solution = Solution()
solution.rotate(nums, k)
print(nums)

